package exercise;

import java.util.Arrays;

/**
 * @author noob
 * @version 1.0
 * @date 2021/3/17 6:09
 * 练习
 */
public class MergeSort {

    public static <E extends Comparable<E>> void sort(E[] arr){

        int left = 0;
        int right = arr.length-1;
        mergesort(arr,left,right);
    }

    private static <E extends Comparable<E>> void mergesort(E[] arr, int left, int right) {

        if(left >= right) {  //注意
            return;
        }

        int mid =  (right+left)/2;
        mergesort(arr,left,mid);
        mergesort(arr,mid+1,right);
        merge(arr,left,mid,right);

    }

    private static <E extends Comparable<E>> void merge(E[] arr, int left, int mid, int right) {

        E[] temp = Arrays.copyOfRange(arr,left,right+1);

        int i = left;
        int j = mid + 1;
        for (int k = left; k <= right ; k++) {

            if( i > mid){
                arr[k] = temp[j-left];
                j++;
            }else if( j > right){
                arr[k] = temp[i-left];
                i++;
            }else if(temp[i-left].compareTo(temp[j-left]) <= 0){
                arr[k] = temp[i-left];
                i++;
            }else{
                arr[k] = temp[j-left];
                j++;
            }

        }
    }

    public static void main(String[] args) {
        Integer []  arr = {1,9,4,3,6,5,7};
        MergeSort.sort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }




}
